Cryptographic systems ensure the privacy and authenticity of messages communicated over communication lines, and generally may be categorized into three distinct types of systems, e.g., privacy systems, identification systems, key exchange system, and digital signature systems.
A privacy or secrecy system prevents the extraction of information by unauthorized parties from messages transmitted over the communications line, thus assuring the sender that it is being read only by the intended receiver.
Identification is used in, for instance, military applications, identification of remote computer users, identification of the person using a smart card or ATM card, identification of employees at their location of employment, and identification of cellular telephone customers. For example, the cellular telephone industry has recently experienced major financial losses from fraud because they do not use sound cryptographic techniques for the identification of telephones that roam outside of their home system.
A digital signature system provides a means for verifying the authenticity of a message, thus assuring the receiver of a message the legitimacy of the message. The notion of a digital signature was apparently first mentioned in the seminal paper by Diffie and Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, Vol. 22, pp. 472-492 (1976), in which they described how a digital signature scheme could be realized from a public key crytosystem. There have been several methods proposed for realizing digital signatures, including the RSA scheme; the ElGamal scheme in T. ElGamal "A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory, Vol. 31, pp. 469-472 (1985); the Fiat-Shamir scheme in "How to prove yourself: Practical solutions to identification and signature problems", Advances in Cryptology (proceedings of Crypto '86), Vol. 263, pp. 186-199 (1987); the Schnorr scheme as described in "Efficient Identification and Signatures for Smart Cards", Advances in Cryptology (Proceedings of Crypto '89), Vol. 435, pp. 239-252 (1990); and the Brickell-McCurley scheme described in "An interactive identification scheme based on discrete logarithms and factoring", Advances in Cryptology (Proceedings of Eurocrypt '90), May 1990.
Interest in digital signatures is increasing rapidly, as evidenced by the recent announcement by the National Institute of Standards and Technology (NIST) of a proposed national standard for digital signatures. It is reasonable to assume that this standard will have at least as much impact as NIST's previous endorsement of the Data Encryption Algorithm, known as DES. The signature standard has not yet been approved, but the current proposal is a variation of the ElGamal scheme. This proposed standard will henceforth be referred to as DSS.
Additionally, in the above secrecy, identification, and signature systems, a secure key exchange may occur. A secure key is an exchange between two parties communicating over an insecure communications line wherein the parties agree upon a common secret piece of information which is utilized in the encryption system. An easy method for accomplishing a secure key exchange was invented by Diffie and Hellman and has been used by Sun Microsystems in security additions to their UNIX networking software.
A fundamental process common to all of these cryptographic systems is the process of a one-way function, f. One party uses an input x, which is kept secret, to produce an output, y=f(x), which is not kept secret. The function f is described as one-way if it is infeasible to invert the function, i.e. given y, it is infeasible to find x so that f(x)=y.
A process used in a number of the cryptographic systems as a one-way function is that of raising an element (g) of a mathematical structure known as a group to a large integer power (e). This process is called exponentiation. The reason for this is that computing g.sup.e is relatively easy, whereas computing e from knowledge of g and g.sup.e is believed to be infeasible.
Several U.S. Patents utilize exponentiation as a one-way function. U.S. Pat. No. 4,424,414, entitled "Exponentiation Cryptographic Apparatus and Method" to Hellman et al., Jan. 3, 1984 discloses a cryptographic system that transmits a computationally secure cryptogram that is generated from a secret transformation of the message sent by the authorized transmitter. This system utilizes an enciphering key K, a deciphering key D, a plaintext message P and a ciphertext C. In operation, the ciphertext C is decrypted into the plaintext P by exponentiating, by modular q arithmetic, the ciphertext C with the deciphering key D.
U.S. Pat. No. 4,200,770, entitled "Cryptographic Apparatus and Method", to Hellman et al., Apr. 29, 1980 discloses a cryptographic system which eliminates the need for a secure channel for exchanging keys. This system also utilizes exponentiation as a one-way function. In this system the first party transforms a first signal x.sub.1, into a second y.sub.1, such that y.sub.1 =a.sup.x.sbsp.1 modq. The second party transforms a third signal x.sub.2 into a fourth signal y.sub.2 such that y.sub.2 =a.sup.x.sbsp.2 modq. The signals y.sub.1 and y.sub.2 are exchanged over a possibly insecure channel. Then both parties compute a fifth signal y.sub.1.sup.x.sbsp.2 =a.sup.x.sbsp.1.sup.x.sbsp.2 =y.sub.2.sup.x.sbsp.1 modq, which can then be used as a secret key.
One of the fundamental problems that arises in the implementation of the above exponentiation process is the difficulty of carrying out exponentiation of one element g in a group to a large integer power e.
The process most often used for computing a power g.sup.e is known as the binary method, and is described in detail in a book by D. E. Knuth, The Art of Computer Programming, Vol 2, Seminumerical Algorithms, Second Edition (1981). In the binary method, g.sup.e is computed by first converting e into its binary representation. For example, if e=23, this binary representation is 10111. Thereafter, each occurrence of a 1 in the binary representation is replaced by a SX and each 0 is replaced by a S. Thus the binary representation in the example above is transformed to SX S SX SX SX. In this transform, S stands for the arithmetic squaring of the prior value of the rule and X stands for the arithmetic multiplication of the prior value of the rule. Additionally, for the proper function of this rule, the first SX is removed. Thus, the final rule in the example above is SSXSXSX, which translates into square, square, multiply by g, square, multiply by g, square, and multiply by g. This involves successively computing g.sup.2, g.sup.4, g.sup.5, g.sup.10, g.sup.11, g.sup.22, and finally arriving at g.sup.23. As can be seen this is much faster than multiplying g by itself 22 times.
Depending on what group is selected for the cryptographic scheme, the multiplications are often fairly time-consuming operations. For example, if the group is the set of residue classes modulo an integer (n) of size around 2.sup.512, as might, for example, be used in the ElGamal, DSS, or RSA schemes, then the multiplications involve arithmetic on very large integers and are relatively complicated. Using the above binary method, g.sup.e may be computed using at most 2 log.sub.2 e modular multiplications. It is desirable to find a method for computing g.sup.e that requires as few multiplications as possible.
The binary method just described is in fact a special case of the method based on addition chains for the exponent e, which is also described in The Art of Computer Programming. Short addition chains give rise to relatively good methods for computing g.sup.e, i.e., methods that require few multiplications in the group.
One fundamental limitation on addition chains is that the number of group multiplications using an addition chain is bounded below by the length of the chain, and this is in turn bounded below by the number of binary digits in the exponent e. Thus, this scheme would be limited to 512 multiplications for a 512 bit exponent. It follows that a method based on addition chains alone cannot yield a method using fewer multiplications.
For some special types of groups (G), faster methods are known. In particular, for the case of exponentiation in a finite field of the form GF (2.sup.n), methods exist that exploit the fact that squaring an element in this group can often be done quickly in hardware. Details for this method can be found in the following articles: Agnew, Mullin and Vanstone, "Fast exponentiation in GF(2.sup.n), Advances in Cryptology-Eurocrypt '88, Vol. 330, pp. 251-255 (1988); Beth, Cook and Gollman, "Architectures for exponentiation in GF(2.sup.n)", Advances in Cryptology-Crypto '86, Vol. 263, pp. 302-310 (1986); and Stinson, "Some observations on parallel algorithms for fast exponentiation in GF(2.sup.n)", Siam J. Comput., Vol. 19, pp. 711-717 (1990). The major drawback to these methods is the limitation to the groups GF(2.sup.n), where the current difficulty of inverting the exponentiation function in these groups dictates that n be fairly large.